#include "CGR.h"
#include "TEST.cpp"

bool    CGR::isLegalSubnet ( TwoTerCoarseNet &snet ) {
  /* 
   * GIVEN : s, t, edges
   * GOAL :  return if the given subnet is connected 
   *  */

  /* build graph */
  map<int,set<int>  >  graph;
  for ( set<int>::iterator it= snet.edges.begin(); it!= snet.edges.end(); it++ ) {
    if ( graph.count ( E[(*it)].srcPoint )!=0 )
      graph[E[(*it)].srcPoint].insert ( E[(*it)].snkPoint );
    else {
      set<int>  myset;
      myset.insert ( E[(*it)].snkPoint );
      graph.insert ( make_pair ( E[(*it)].srcPoint, myset ) );
    }
    if ( graph.count ( E[(*it)].snkPoint )!=0 )
      graph[E[(*it)].snkPoint].insert ( E[(*it)].srcPoint );
    else {
      set<int>  myset;
      myset.insert ( E[(*it)].srcPoint );
      graph.insert ( make_pair ( E[(*it)].snkPoint, myset ) );
    }
  }   //  connectivity graph is built
  /* check if exist rebundant edges */
  if ( graph[snet.s].size()!=1 || graph[snet.t].size()!=1 ) {
    cout << "SUBNET ERROR : edge rebundancy" << endl;
    return  false;
  }
  /* check if is a legal subnet */
  int curr_node = snet.s;
  set<int>  visited_nodes;
  int num_visited_edges = 0;
  while ( num_visited_edges < snet.edges.size() ) {
    /* delete adjacent nodes that are(is) already visited */
    for ( set<int>::iterator it = graph[curr_node].begin(); it!= graph[curr_node].end(); it++ ) {
      if ( visited_nodes.find(*it) != visited_nodes.end() )
        graph[curr_node].erase (*it);
    }
    if ( graph[curr_node].size()!=1 ) {
      cout << "SUBNET ERROR : illegal subnet" << endl;
      return  false;
    }
    visited_nodes.insert ( curr_node );
    curr_node = *(graph[curr_node].begin());
    ++ num_visited_edges;
  }
  assert ( curr_node == snet.t );
  return  true;
}

string  CGR::getSubnetType ( TwoTerCoarseNet &snet ) {
  /* determine whether the given subnet belongs to one of the pre-defined patterns */

  /* number of flat segment == number of continuous segments */
  int number_flat_segments = 1;
  vector<int> edge_vector ( snet.edges.begin(), snet.edges.end() );
  /* determine if it is a flat segment */
  for ( size_t i=0; (i+1) != edge_vector.size(); i++ ) {
    if ( edge_vector[i+1]==edge_vector[i]+1 )
      continue;
    number_flat_segments++;
  }
  if ( number_flat_segments == 1 )
    return  "flat subnet";
  if ( number_flat_segments == 2 )
    return  "L shape subnet";
  if ( number_flat_segments == 3 )
    return  "Z or U shape subnet";

  return  "other";
}

bool  CGR::isSubnetWithFlatEndingPoints ( TwoTerCoarseNet &snet ) {
  return  ( V[snet.s].x==V[snet.t].x && V[snet.s].y==V[snet.t].y 
      ||  V[snet.s].y==V[snet.t].y && V[snet.s].z==V[snet.t].z 
      ||  V[snet.s].z==V[snet.t].z && V[snet.s].x==V[snet.t].x  );
}

bool  compare_subnet_with_smaller_weight ( const pair<TwoTerCoarseNet, double> &p1, const pair<TwoTerCoarseNet, double> &p2 ) {
  return  p1.second < p2.second;
}

void  CGR::findCompleteUShapeCandidateSubnetSetForFlatSegment ( GridBox &box, subnetIdType subnet_id, int M2 ) {
  TwoTerCoarseNet &snet = bnets[ subnet_id.first ].subnets[ subnet_id.second ];
  /* all the possible candidate subnets */
  /* key = temp_candidate_subnets 
   * value = subnet weight */
  vector<pair<TwoTerCoarseNet, double> > full_pair_candidate_subnets_to_subnet_weight;
  assert ( snet.s != snet.t );
  if ( isSubnetWithFlatEndingPoints(snet) == false ) 
    return;
  /* generate candidate subnets for subnet (i,j) */
  int first_edge = *(snet.edges.begin());
  /* find candidate U-shape routes in same layer 
   * since the subnet is in BFR, so only need to figure out which edges are included in new route */
  int c1,c2,c3,c4,c5,c6;
  if ( V[snet.s].y==V[snet.t].y && V[snet.s].z==V[snet.t].z  ) {
    for ( int z1 = 0; z1 < numLayers; z1++ ) {
      if ( horizCaps[z1] == 0 )
        continue;
      for ( int y = box.y0; y < box.y0+box.dy; y++ ) {
        c1 = xyzToGridNetTerminalId ( V[snet.s].x, y, z1 );
        c2 = xyzToGridNetTerminalId ( V[snet.t].x, y, z1 );
        for ( int z2 = 0; z2 < numLayers; z2++ ) {
          if ( vertCaps[z2] == 0 )
            continue;
          TwoTerCoarseNet candidate_snet;
          candidate_snet.s = snet.s;
          candidate_snet.t = snet.t;

          c3 = xyzToGridNetTerminalId ( V[snet.s].x, V[snet.s].y, z2 );
          c4 = xyzToGridNetTerminalId ( V[snet.t].x, V[snet.t].y, z2 );
          c5 = xyzToGridNetTerminalId ( V[snet.s].x, y, z2 );
          c6 = xyzToGridNetTerminalId ( V[snet.t].x, y, z2 );
          set<int>  flat_segment_1 = getFlatSegment ( snet.s, c3 );
          set<int>  flat_segment_2 = getFlatSegment ( c3, c5 );
          set<int>  flat_segment_3 = getFlatSegment ( c5, c1 );
          set<int>  flat_segment_4 = getFlatSegment ( c1, c2 );
          set<int>  flat_segment_5 = getFlatSegment ( c2, c6 );
          set<int>  flat_segment_6 = getFlatSegment ( c6, c4 );
          set<int>  flat_segment_7 = getFlatSegment ( c4, snet.t );
          candidate_snet.edges.insert ( flat_segment_1.begin(), flat_segment_1.end() );
          candidate_snet.edges.insert ( flat_segment_2.begin(), flat_segment_2.end() );
          candidate_snet.edges.insert ( flat_segment_3.begin(), flat_segment_3.end() );
          candidate_snet.edges.insert ( flat_segment_4.begin(), flat_segment_4.end() );
          candidate_snet.edges.insert ( flat_segment_5.begin(), flat_segment_5.end() );
          candidate_snet.edges.insert ( flat_segment_6.begin(), flat_segment_6.end() );
          candidate_snet.edges.insert ( flat_segment_7.begin(), flat_segment_7.end() );
          /* push pair of new candidate subnet and its weight */
          full_pair_candidate_subnets_to_subnet_weight.push_back ( make_pair ( candidate_snet, computeSubnetEdgeWeight ( candidate_snet) ) );
        }
      }
    }
  }
  if ( V[snet.s].z==V[snet.t].z && V[snet.s].x==V[snet.t].x  ) {
    for ( int z1 = 0; z1 < numLayers; z1++ ) {
      if ( vertCaps[z1] == 0 )
        continue;
      for ( int x = box.x0; x < box.x0+box.dx; x++ ) {
        c1 = xyzToGridNetTerminalId ( x, V[snet.s].y, z1 );
        c2 = xyzToGridNetTerminalId ( x, V[snet.t].y, z1 );
        for ( int z2 = 0; z2 < numLayers; z2++ ) {
          if ( horizCaps[z2] == 0 )
            continue;
          TwoTerCoarseNet candidate_snet;
          candidate_snet.s = snet.s;
          candidate_snet.t = snet.t;

          c3 = xyzToGridNetTerminalId ( V[snet.s].x, V[snet.s].y, z2 );
          c4 = xyzToGridNetTerminalId ( V[snet.t].x, V[snet.t].y, z2 );
          c5 = xyzToGridNetTerminalId ( x, V[snet.s].y, z2 );
          c6 = xyzToGridNetTerminalId ( x, V[snet.t].y, z2 );
          set<int>  flat_segment_1 = getFlatSegment ( snet.s, c3 );
          set<int>  flat_segment_2 = getFlatSegment ( c3, c5 );
          set<int>  flat_segment_3 = getFlatSegment ( c5, c1 );
          set<int>  flat_segment_4 = getFlatSegment ( c1, c2 );
          set<int>  flat_segment_5 = getFlatSegment ( c2, c6 );
          set<int>  flat_segment_6 = getFlatSegment ( c6, c4 );
          set<int>  flat_segment_7 = getFlatSegment ( c4, snet.t );
          candidate_snet.edges.insert ( flat_segment_1.begin(), flat_segment_1.end() );
          candidate_snet.edges.insert ( flat_segment_2.begin(), flat_segment_2.end() );
          candidate_snet.edges.insert ( flat_segment_3.begin(), flat_segment_3.end() );
          candidate_snet.edges.insert ( flat_segment_4.begin(), flat_segment_4.end() );
          candidate_snet.edges.insert ( flat_segment_5.begin(), flat_segment_5.end() );
          candidate_snet.edges.insert ( flat_segment_6.begin(), flat_segment_6.end() );
          candidate_snet.edges.insert ( flat_segment_7.begin(), flat_segment_7.end() );
          /* push pair of new candidate subnet and its weight */
          full_pair_candidate_subnets_to_subnet_weight.push_back ( make_pair ( candidate_snet, computeSubnetEdgeWeight ( candidate_snet) ) );
        }
      }
    }
  }

  /* Select the top M2 candidate subnets with least weight */
  sort ( full_pair_candidate_subnets_to_subnet_weight.begin(), full_pair_candidate_subnets_to_subnet_weight.end(), compare_subnet_with_smaller_weight );

  for ( vector<pair<TwoTerCoarseNet, double> >::iterator itr = full_pair_candidate_subnets_to_subnet_weight.begin(); 
      itr < full_pair_candidate_subnets_to_subnet_weight.begin()+M2 && itr != full_pair_candidate_subnets_to_subnet_weight.end(); itr++ )
    bnets[subnet_id.first].candidate_subnets[subnet_id.second].push_back ( (*itr).first );
}

void  selfIncremental ( vector<int> &counter, vector<int> bit_range ) {
  assert ( counter.size()==bit_range.size() );
  if ( counter[counter.size()-1]+1 < bit_range[bit_range.size()-1] ) {
    counter[counter.size()-1]++;
    return;
  }
  /* cnt tot number */
  int total_number = 1, cnt = 0;
  for ( size_t i=0; i< bit_range.size(); i++ )
    total_number *= bit_range[i];
  /* self incremental */
  int last_bit_count = 1;
  bool  cin = true;
  while ( cnt < total_number ) {
    if ( last_bit_count > counter.size() )
      return;
    counter[counter.size()-last_bit_count] = 0;
    ++ last_bit_count;
    if ( counter[counter.size()-last_bit_count]+1 < bit_range[counter.size()-last_bit_count] ) {
      counter[counter.size()-last_bit_count]++;
      return;
    }
  }
}

vector<int>   getCandidateSubnetIdThroughCandidateNetRouteId ( vector<int> &bit_range, int net_route_id ) {

  vector<int> candidate_subnetid_vector;
  for ( int i = bit_range.size()-1; i >=0; i-- ) {
    candidate_subnetid_vector.push_back ( net_route_id % bit_range[i] );
    net_route_id = net_route_id / bit_range[i];
  }
  reverse ( candidate_subnetid_vector.begin(), candidate_subnetid_vector.end() );
  return  candidate_subnetid_vector;

}

vector<NetRoute> CGR::getCompleteCandidateSet ( vector<vector<TwoTerCoarseNet> > candidate_subnets, int upper_bound_number ) {
  vector<NetRoute>  candidate_routes;
  bool  debug_mode = false;
  int total_number = 1;
  vector< int > selected_subnets ( candidate_subnets.size(), 0 );
  vector< int > &ref_selected_subnets = selected_subnets;
  vector< int > subnets_size ( candidate_subnets.size(), 0 );
  for ( size_t i=0; i < candidate_subnets.size(); i++ ) {
    subnets_size[i] = candidate_subnets[i].size();
    total_number *= subnets_size[i];
  }
  assert ( total_number != 0 );
  for ( int i=0; i <min(upper_bound_number, total_number); i++ ) {
    /* build candidate route with candidate subnets in index vector */
    vector<TwoTerCoarseNet> subnets;
    for ( size_t j= 0; j < candidate_subnets.size(); j++ )
      subnets.push_back ( candidate_subnets[j][ref_selected_subnets[j]] );
    /* construct a new candidate net route using subnet vector */
    NetRoute  new_netroute ( subnets );
    candidate_routes.push_back ( new_netroute );
    /* For Debug */
    if ( debug_mode ) {
      cout << "candidate net route " << i << " : edge number = "  << new_netroute.edges.size() << endl;
      cout << "number of subnets = " << candidate_subnets.size() << endl;
      for ( size_t j= 0; j < candidate_subnets.size(); j++ )
        cout << ref_selected_subnets[j] << ",";
      cout << endl;
    }
    /* End */
    selfIncremental ( ref_selected_subnets, subnets_size );
  }
  return  candidate_routes;
}

void  CGR::addNewCandidateRoutes ( int bnet_index, int upper_bound_number ) {

  bool  debug_mode = false;
  int total_number = 1;
  /* simulate a counter */
  vector< int > selected_subnets ( bnets[bnet_index].candidate_subnets.size(), 0 );
  vector< int > &ref_selected_subnets = selected_subnets;
  vector< int > subnets_size ( bnets[bnet_index].candidate_subnets.size(), 0 );
  for ( size_t i=0; i < bnets[bnet_index].candidate_subnets.size(); i++ ) {
    subnets_size[i] = bnets[bnet_index].candidate_subnets[i].size();
    total_number *= subnets_size[i];
  }
  assert ( total_number != 0 );
//  cout << "Before : " << bnets[bnet_index].candidate_routes.size() << endl;
  for ( int i=0; i <min(upper_bound_number, total_number); i++ ) {
    /* build candidate route with candidate subnets in index vector */
    vector<TwoTerCoarseNet> subnets;
    for ( size_t j= 0; j < bnets[bnet_index].candidate_subnets.size(); j++ )
      subnets.push_back ( bnets[bnet_index].candidate_subnets[j][ref_selected_subnets[j]] );
    /* construct a new candidate net route using subnet vector */
    NetRoute  new_netroute ( subnets );
    bnets[bnet_index].candidate_routes.push_back ( new_netroute );
    /* For Debug */
    if ( debug_mode ) {
      cout << "candidate net route " << i << " : edge number = "  << new_netroute.edges.size() << endl;
      cout << "number of subnets = " << bnets[bnet_index].candidate_subnets.size() << endl;
      for ( size_t j= 0; j < bnets[bnet_index].candidate_subnets.size(); j++ )
        cout << ref_selected_subnets[j] << ",";
      cout << endl;
    }
    /* End */
    selfIncremental ( ref_selected_subnets, subnets_size );
  }
//  cout << "After : " << bnets[bnet_index].candidate_routes.size() << endl;
}

/* 
 * This function has only one parameter of a box reference and only needs to run once per box iteration.
 * Here is the function of this module : 
 *  1. Clear everything and build a vector to store all the edges in box.
 *  2. Check for all the nets and select the related nets into a vector called bnets, which stores all the modified nets. And these nets are the objectives to deal with in this box iteration. Each bnet has its own old index, terminal pin vector, segments vector and edge set, like what a common net does.
 *  */
void    CGR::genModifiedNetsInBox (GridBox &box) {
  /* put all the edges inside bounding box into box.E_id */
  E_id.clear();
  bool  debug_mode = false;
  for ( int k = 0; k < numLayers; k++ )   {
    for ( int j=box.y0; j< box.y0+box.dy; j++ )
      for ( int i=box.x0; i< box.x0+box.dx-1; i++ ) {
        int edge_id = return_edge_id ( i,j,k,0 );
        map_from_edge_id_to_index_in_E_id.insert (  make_pair ( edge_id, E_id.size() ) );
        E_id.push_back ( edge_id );
      }
    for ( int i=box.x0; i< box.x0+box.dx; i++ ) 
      for ( int j=box.y0; j< box.y0+box.dy-1; j++ )  {
        int edge_id = return_edge_id ( i,j,k,1 );
        map_from_edge_id_to_index_in_E_id.insert (  make_pair ( edge_id, E_id.size() ) );
        E_id.push_back ( edge_id );
      }
  }
  for ( int j=box.y0; j< box.y0+box.dy; j++ )
    for ( int i=box.x0; i< box.x0+box.dx; i++ ) 
      for ( int k = 0; k < numLayers-1; k++ )  {
      int edge_id = return_edge_id ( i,j,k,2 );
      map_from_edge_id_to_index_in_E_id.insert (  make_pair ( edge_id, E_id.size() ) );
      E_id.push_back ( edge_id );
    }
  cout << "Built Grid Box " << endl;
  /* end */
  bnets.clear();
  for ( size_t i=0; i<nets.size(); i++ ) {
    CoarseNet   modified_net_inbox = genSingleModifiedNetInBox (nets[i], box );
    if ( modified_net_inbox.terminal_pins.size() > 0 ) {
      bnets.push_back ( modified_net_inbox );
    }
  }
  cout << "In this box iteration, the number of modified nets = " << bnets.size() << endl;

  /* merge short segments into longer ones */
  for ( size_t i=0; i<bnets.size(); i++ ) {
    CoarseNet &net = bnets[i];
    vector<int>  edges ( net.edges.begin(), net.edges.end() );
    net.sg.clear();
    /* the flat segment has a very good property that all the edge id numbers are continuous. */
    vector<int>::iterator itr_edge = edges.begin();
    vector<int>::iterator itr_segment_begin = edges.begin(); 
    vector<int>::iterator itr_segment_end;

    while ( (itr_edge+1) != edges.end() ) {
      if ( *(itr_edge+1) == (*itr_edge)+1 && E[*itr_edge].snkPoint==E[*(itr_edge+1)].srcPoint && E[*itr_edge].type==E[*(itr_edge+1)].type ) {
        itr_edge++;
        continue;
      }
      itr_segment_end = itr_edge;

      Segment merged_segment;
      merged_segment.s = E[*itr_segment_begin].srcPoint;
      merged_segment.t = E[*itr_segment_end].snkPoint;
      merged_segment.type = E[*itr_segment_begin].type;

      net.sg.push_back ( merged_segment );
      itr_edge++;
      itr_segment_begin = itr_edge;
    }
    itr_segment_end = itr_edge;

    Segment merged_segment;
    merged_segment.s = E[*itr_segment_begin].srcPoint;
    merged_segment.t = E[*itr_segment_end].snkPoint;
    merged_segment.type = E[*itr_segment_begin].type;

    net.sg.push_back ( merged_segment );
  }
  cout << "Segment Merged" << endl;

  for ( size_t i=0; i < bnets.size(); i++ )
    if ( debug_mode== true ) {
      cout << bnets.size() << " " << bnets[i].old_index << " " << bnets[i].terminal_pins.size() << " " << bnets[i].edges.size() << endl;
      printNet ( bnets[i] );
    }
//  exit(0);
}

/* 
 * This function exectues right after "genModifiedNetsInBox" and only runs once per box iteration. This function implements the initialization for followed ILP iterations and enables the followed functions can be executed in a normal way.
 *  1. "modified_net_type" is defined for each modified net to show whether it is connected or not. Since this property will keep unchanged during the same box iteration, this vector only needs to compute once and be mapped to each modified net until the box iterations ends. And the modified net type is determined by calling function "isConnected" by reading the edge set of bnet.
 *  2. Implement net decomposition for connected modified net. Net decomposition generates a vector of subnets, each of which contains two terminal pins and edge set. 
 *  3. As for disconnected modified net, split the boundary terminal pins into disjoint sets and hold it. 
 *  4. Store base route for both types of modified nets. For type 0, the candidate route vector is initialized with a net route containing both subnet vector and edge set. Candidate subnet is also initialized with correct number of entries, each of which is a vector of one subnet, i.e. the original subnet. For type 1, there is no candidate subnets and the only item in candidate route has only a edge set.
 * */
void  CGR::initializeLoop ( ) {
  /* build an integer array store the net type of modified nets */

  for ( size_t i=0; i < bnets.size(); i++ ) {
    CoarseNet &net = bnets[i];

    if ( isConnected ( net ) ) {
      modified_net_type.push_back ( 0 );

      netDecomposition ( net );
      /* initialize with base route */
      bnets[i].candidate_subnets.clear();
      bnets[i].candidate_routes.clear();
      for ( size_t j = 0; j < bnets[i].subnets.size(); j++ ) {
        vector < TwoTerCoarseNet > myset;
        myset.push_back ( bnets[i].subnets[j] );
        bnets[i].candidate_subnets.push_back ( myset );
      }
      NetRoute  base_route ( bnets[i].subnets );
      bnets[i].candidate_routes.push_back ( base_route );
    }
    else {
      modified_net_type.push_back ( 1 );
      splitBoundaryTerminalPins ( net ); 

      /* initialize with base route */
      bnets[i].candidate_routes.clear();
      NetRoute base_route;
      base_route.edges = bnets[i].edges;
      bnets[i].candidate_routes.push_back ( base_route );
    }
  }

  /* the edge util here are the directly from input routes */
  findCongestedEdges ();
  cout << "Found congested edges" << endl;
}

/* 
 * This function is executed right after each time ILP is solved. In previous function of solving ILP, the primal solution and dual solution will give which among candidate routes per net is selected and which value should be assigned to edge weight. 
 *  1.  re-initialize the candidate_routes with new solution
 *  2.  re-calculate congestion edges
 *  3.  re-decompose net and initialize the candidate_subnets vector
 * */
void  CGR::readyForNextIteration (GridBox &box ) {

  /* re-initialize the candidate routes with new solution 
   * replace the set<int> edges in net with the edge set of selected candidated route */
  for ( size_t i=0; i< bnets.size(); i++ ) {
    /* update the subnets of given net */
    bnets[i].subnets.clear();
    bnets[i].candidate_subnets.clear();
    if ( modified_net_type[i] == 0 ) {
      netDecomposition ( bnets[i] );
      /* initialize the candidate subnet */
      for ( size_t j=0; j < bnets[i].subnets.size(); j++ ) {
        
        TwoTerCoarseNet base_subnet;
        base_subnet.s = bnets[i].subnets[j].s;
        base_subnet.t = bnets[i].subnets[j].t;
        base_subnet.edges = bnets[i].subnets[j].edges;

        vector< TwoTerCoarseNet > candidate_snet;
        candidate_snet.push_back ( base_subnet );
        bnets[i].candidate_subnets.push_back ( candidate_snet );
      }
    }
  }

  /* re-calculate congested edges inside box */
  for ( vector<int>::iterator itr_edge = E_id.begin(); itr_edge != E_id.end(); itr_edge++ ) 
    E[*itr_edge].util = 0;
  for ( size_t i=0; i< bnets.size(); i++ ) {
    for ( set<int>::iterator itr_edge = bnets[i].edges.begin(); itr_edge!= bnets[i].edges.end(); itr_edge++ ) {
      ++ E[*itr_edge].util;
    }
  }
  findCongestedEdges ();

  subnets_to_expand.clear();
  for ( vector<pair<int,double> >::iterator itr_edge = congested_edges.begin(); itr_edge!=congested_edges.end(); itr_edge++ ) {
    int edge_id = (*itr_edge).first;
    for ( size_t i=0; i< bnets.size(); i++ ) {
      if ( modified_net_type[i] == 1 )
        continue;
      for ( size_t j=0; j< bnets[i].subnets.size(); j++ ) {
        /* 
         * for each subnet (i,j), check if it contains the edge
         */
        TwoTerCoarseNet &snet = bnets[i].subnets[j];
        bool is_edge_contained_in_this_subnet = (snet.edges.find( (*itr_edge).first ) != snet.edges.end() );
        if ( is_edge_contained_in_this_subnet == false )  //  if the subnet does not contain that edge, then nothing happens.
          continue;
        subnets_to_expand.insert ( make_pair(i,j) );
      }
    }
  }
  int M2 = 4;
  int M3 = 300;
  for ( set<subnetIdType>::iterator itr = subnets_to_expand.begin(); itr != subnets_to_expand.end(); itr++ ) {
    /* find up to M2 candidate routes for given subnet */
    findCompleteUShapeCandidateSubnetSetForFlatSegment ( box, *itr, M2 ); 
  }
  cout << "generated at most " << M2 << " candidate routes for each subnet " << endl;
  /* 
   * This is a module connected to another module to add columns.
   */
  for ( vector<CoarseNet>::iterator itr_net = bnets.begin(); itr_net != bnets.end(); itr_net ++ ) {
    int num_routes = 1;
    int ii = itr_net - bnets.begin();
    if ( modified_net_type[ii] != 0 ) 
      continue; 
    addNewCandidateRoutes ( ii, M3 );
  }
  cout << "combined at most " << M3 << " candidate net routes" << endl;
}

/* 
 *  This function merges the net edges inside bounding box together with the parts that lay outside the bounding box. Also refine the segments and check the legality. 
 * */
void  CGR::refreshNetSegments (void) {

  cout << "bnets.size = " << bnets.size() << endl;
  for ( size_t i=0; i< bnets.size(); i++ ) {
    int old_index=  bnets[i].old_index;
    assert ( map_from_net_old_index_to_idnex_in_nets.count ( old_index )==1 );
    /* map to the original net route using old index */
    int index_in_nets = map_from_net_old_index_to_idnex_in_nets [old_index];
    /* erase all the edges inside the bounding box */
    for ( set<int>::iterator itr_edge=nets[index_in_nets].edges.begin(); itr_edge!=nets[index_in_nets].edges.end(); ) {
      if ( find ( E_id.begin(), E_id.end(), *itr_edge ) != E_id.end() )
        nets[index_in_nets].edges.erase ( itr_edge++ );
      else
        ++itr_edge;
    }
    /* insert those edges inside bounding box using the solution of ILP */
    nets[index_in_nets].edges.insert ( bnets[i].edges.begin(), bnets[i].edges.end() );
    /* update segment vector in net[index_in_nets] */
    generateLongestSegments ( index_in_nets );
  }
}

/* 
 *  This function only needs the edge set of the given net and generate a segment vector, each of which are made as long as possible.
 *  */
void  CGR::generateLongestSegments ( int index_in_nets ) {

  CoarseNet &net = nets[index_in_nets];
  vector<int>  edges ( net.edges.begin(), net.edges.end() );
  /* the flat segment has a very good property that all the edge id numbers are continuous. */
  vector<int>::iterator itr = edges.begin();
  vector<int>::iterator itr_begin = edges.begin(); 

  net.sg.clear();
  while ( itr_begin != edges.end() ) {
    if ( (itr+1) == edges.end() || (*itr)+1!=(*(itr+1)) || E[*itr].snkPoint != E[*(itr+1)].srcPoint ) {
      assert ( E[*itr].type == E[*itr_begin].type );
      Segment merged_segment;
      merged_segment.s = E[*itr_begin].srcPoint;
      merged_segment.t = E[*itr].snkPoint;
      merged_segment.type = E[*itr].type;
      net.sg.push_back ( merged_segment );
      itr_begin = itr+1;
    }
    ++ itr;
  }
//  printSegmentEdges ( new_segment );
}

/*
 * funtions : measure the performance metrics
 */

/* 
 * ACE ( y% ) 
 *  the average congestion ratio of the top y% congested edges
 *  FYI : here we skip all the complete blockages, i.e. edges with zero capacity 
 *  */
double  CGR::getACE ( double y ) {
  vector<double>  edge_congestion_ratio;
  for ( vector<GridEdge>::iterator itr_edge = E.begin(); itr_edge != E.end(); itr_edge++ ) 
    if ( (*itr_edge).cap != 0 )
      edge_congestion_ratio.push_back ( (double)(*itr_edge).util/(*itr_edge).cap );
  sort ( edge_congestion_ratio.begin(), edge_congestion_ratio.end() );
  reverse ( edge_congestion_ratio.begin(), edge_congestion_ratio.end() );

  double  sum_congestion_edge = 0;
  int edge_count = 0;
  for ( size_t i=0; i < edge_congestion_ratio.size() * y ; i++ ) {
    sum_congestion_edge += edge_congestion_ratio[i];
    ++ edge_count;
  }

  return  (double)sum_congestion_edge / edge_count;
}

double  CGR::getNetCongestioRatio ( CoarseNet &net ) {
  double  g_net= 0;
  for ( set<int>::iterator itr_edge = net.edges.begin();
        itr_edge != net.edges.end();  itr_edge ++ )
    if ( E[*itr_edge].cap > 0 && (double)E[*itr_edge].util/E[*itr_edge].cap > g_net )
      g_net = (double)E[*itr_edge].util/E[*itr_edge].cap;
  if ( g_net == 0 )
    return  100;  //  BAD NET ROUTING
  return  g_net;
}

/* 
 * WCI ( TCR ) 
 *  the number of nets with congestion ratio greater than TCR 
 *   where the congestion ratio of net is defined as the highest congestion ratio of net edges
 *    FYI : ignore congestion ratio of all the edges with zero capacity */
int CGR::getWCI ( double TCR ) {
  int counter = 0;

  for ( size_t i = 0; i < nets.size(); i++ ) {
    double  net_congestion_ratio = getNetCongestioRatio ( nets[i] );
    if ( net_congestion_ratio > TCR )
      counter++;
  }
  return  counter;
}

double  CGR::getGlobalObjVal (void) {
  double  global_obj_val = 0;
  for ( size_t i=0; i < E.size(); i++ ) {
    if ( E[i].type=="VIA" )
      continue;
    double  t_e = -10000000; 
    for ( size_t j = 0; j< jsize; j++ )
      t_e = max ( t_e, mj[j]*E[i].util + bj[j]*E[i].cap );
    global_obj_val += t_e;
  }
  return  global_obj_val;
}

void  CGR::getInputGlobalRoutingInfo (void) {
  cout << "TOT_OFL = " << getTotalOverFlow () <<endl;
  cout << "GLOBAL OBJVAL = " << getGlobalObjVal () << endl;
  cout << "WCI(100) = " << getWCI ( 1 ) << endl;
  cout << "WCI(90) = " << getWCI ( 0.9 ) << endl;
  cout << "ACE(0.5%) = " << getACE ( 0.005 ) << endl;
  cout << "ACE(1%) = " << getACE ( 0.01 ) << endl;
  cout << "ACE(2%) = " << getACE ( 0.02 ) << endl;
  cout << "ACE(5%) = " << getACE ( 0.05 ) << endl;
  cout << "ACE(10%) = " << getACE ( 0.1 ) << endl;
  cout << "ACE(20%) = " << getACE ( 0.5 ) << endl;
}

/* brutely remove all the bad edges which has non-zero utilization but zero capacity */
bool  CGR::isLegalSegment ( Segment seg ) {
  if ( seg.type == "VIA" )
    return  true;
  if ( seg.type == "HORIZ" ) {
    return  ( horizCaps[V[seg.s].z] != 0 );
  }
  if ( seg.type == "VERT" ) {
    return  ( vertCaps[V[seg.s].z] != 0 );
  }
  cout << "ERROR" << endl;
  exit(0);
}

int   CGR::countBadEdges ( void ) {
  /* return the number of bad edges in global grid */
  int number_bad_edges = 0;
  for ( vector<GridEdge>::iterator itr_edge = E.begin(); itr_edge != E.end(); itr_edge ++ ) {
    if ( (*itr_edge).cap==0 && (*itr_edge).util!=0 )
      number_bad_edges++;
  }
  return  number_bad_edges;
}
